package top.lcm889.oj.leetcodeTop200;

import java.util.*;

/**
 * @author Coder-lcm
 * @date 2021/4/10
 */
public class LC229_求众数2 {
    public List<Integer> majorityElement(int[] nums) {
        int len = nums.length;
        if (len == 0) return new ArrayList<>();
        if (len == 1) return Arrays.asList(nums[0]);
        Map<Integer, Integer> rise = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (rise.containsKey(nums[i])) {
                rise.put(nums[i], rise.get(nums[i]) + 1);
                continue;
            }
            rise.put(nums[i], 1);
        }
        List<Integer> res = new ArrayList<>();
        for (Integer key : rise.keySet()) {
            if (rise.get(key) > ( len / 3)) {
                res.add(key);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        LC229_求众数2 test = new LC229_求众数2();
        List<Integer> res = test.majorityElement(new int[]{3, 2, 3});
        res.forEach(e -> System.out.print(e + ", "));
    }
}
